/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/flood-fill
   @Language: C++
   @Datetime: 19-05-13 14:38
   */

class Solution {
public:
	/**
	 * @param image: a 2-D array
	 * @param sr: an integer
	 * @param sc: an integer
	 * @param newColor: an integer
	 * @return: the modified image
	 */
	vector<vector<int>> floodFill(vector<vector<int> > &image, int sr, int sc, int newColor) {
		// Write your code here
		int n=image.size(), m=image[0].size();
		int color=image[sr][sc];
		unordered_set<int> visit;
		queue<pair<int,int> > q;
		for(q.push(make_pair(sr,sc)); q.size(); q.pop()){
			auto &p=q.front();
			if(p.first<0 || p.first>=n || p.second<0 || p.second>=m) continue;
			if(visit.count(p.second|(p.first<<8))) continue;
			if(image[p.first][p.second]!=color) continue;
			image[p.first][p.second]=newColor;
			visit.insert(p.second|(p.first<<8));
			q.push(make_pair(p.first+1,p.second));
			q.push(make_pair(p.first-1,p.second));
			q.push(make_pair(p.first,p.second+1));
			q.push(make_pair(p.first,p.second-1));
		}
		return image;
	}
};
